WhatsUp interview question

Create a class R to hold key-values pairs. It has a capacity, max number of element it can hold. Adding an element makes it the youngest (most recent). Adding an element above the capacity removes the oldest element. Reading an element makes it the youngest (least recenly touched):

r=new R(10) # capacity = 10
r.put(k1,v1)  // O(1)
r.put(k2,v2)
...
r.put(k10,v10)

r.get(k1) -> v1  // O(1)

# capacity 10
r.put(k11,v11)
r.get(k1) -> undef  
r.get(k2) -> v2 
r.put(k12, v12)
r.get(k3) -> undef
r.get(k2) -> v2

Solution

The class will use a hash to hold key-values pairs and a queue to opder the pairs. Hash will guarantee O(1) time for reading and writing.



In [3]:

    
class R:
    def __init__(self,n):
        self.N=n
        self.h={}
        self.q=[]

    def put(self, k, v):
        
        if k in self.h:
            self.h[k] = v
            self.make_it_recent(k)
            return

        if len(self.h) >= self.N: 
            self.remove_the_oldest()
        
        self.h[k] = v
        self.make_it_recent(k)

        
        
        
    def get(self, k):
        self.make_it_recent(k)
        return self.h[k]
    

    def make_it_recent(self, k):
        if k in self.q:
            self.q.remove(k)
        self.q.append(k)
 

    def remove_the_oldest(self):
        if len(self.q)>0 :
            del self.h[self.q[0]]
            del self.q[0]
            
    
    
    def print(self):
        for k in self.q:
            print(k+"="+self.h[k])
        print("---------------")
            
                    
 

r = R(5)
r.put("a","aa")
r.put("b","bb")
r.put("c","cc")
r.put("d","dd")
r.put("e","ee")
r.put("f","ff")
r.print()

r.get("b")
r.print()

r.put("g","gg")
r.print()

r.put("e","eee")
r.print()









    



b=bb
c=cc
d=dd
e=ee
f=ff
---------------
c=cc
d=dd
e=ee
f=ff
b=bb
---------------
d=dd
e=ee
f=ff
b=bb
g=gg
---------------
d=dd
f=ff
b=bb
g=gg
e=eee
---------------



In [16]:

    
%%javascript

function print(s) {
    console.log(s);
    if (typeof element !== 'undefined')
        element.html(element.html() + s + '<br>\n');
}

class R {
    constructor(n) {
        this.N = n;
        this.h = {};
        this.q = [];
    }

    put(k, v) {
        if (k in this.h) {
            this.h[k] = v;
            this.make_it_recent(k);
            return;
        }

        if (Object.keys(this.h).length >= this.N) {
            this.remove_the_oldest();
        }

        this.h[k] = v;
        this.make_it_recent(k);
    }

    get(k) {
        this.make_it_recent(k);
        return this.h[k];
    }


    make_it_recent(k) {
        const i = this.q.indexOf(k);
        if (i !== -1) {
            this.q.splice(i, 1);
        }
        this.q.push(k);
    }


    remove_the_oldest() {
        if (this.q.length > 0) {
            delete this.h[this.q[0]];
            this.q.shift();
        }
    }

    print() {
        for (let k of this.q) {
            print(`${k} -> ${this.h[k]}`);
        }
        print("------------------");
    }


}

const r = new R(5);
r.put("a", "aa");
r.put("b", "bb");
r.put("c", "cc");
r.put("d", "dd");
r.put("e", "ee");
r.put("f", "ff");
r.print();

r.get("b");
r.print();

r.put("g", "gg");
r.print();

r.put("e", "eee");
r.print();